In general, a network device sends and receives network packets that have widely varying characteristics and functions. For example, certain packets contain network management control information, while others may carry content for a real-time application, such as streaming video or Voice-over-IP telephony.
Because the amount and types of network traffic being transmitted, analyzed, routed, and filtered by computer networks continues to grow, many networks offer quality of service (QoS) guarantees beyond best-effort service in order to assure a certain level of performance. For example, a network may guarantee a certain maximum delay from a particular source to a particular destination. As another example, a network may promise to provide a guaranteed level of bandwidth to a particular node. These QoS guarantees are often grouped into priority levels, with each priority level providing a different level of service.
The mechanisms required to achieve QoS guarantees are implemented in network devices, such as routers, switches, and firewall devices. Typically, such a device contains a number of priority queues corresponding to the different priority levels. As packets are received by the network device, they are analyzed and classified according to their priority. Each packet is then assigned to one of the many priority queues within the network device, where the packet is then buffered in order to await processing. Conventional priority queues within a typical network device must be deep, requiring a significant amount of memory, in order to accommodate unpredictable bursts of network packets that may be classified as one particular priority. The network device processes the packets in the priority queues according to the requirements specified by the corresponding QoS guarantee in order to achieve the requisite level of service.